#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAXMATRIXSIZE 100
#define MAXSTACKSIZE 100

struct Offsets {
    short int Vert;
    short int Horiz;
};

struct MazePosition {
    short int Row;
    short int Col;
    short int Dir;
};

typedef struct MazePosition ElementType;

typedef struct SNode* PtrToSNode; 

struct SNode {
    ElementType Data;
    PtrToSNode Next;
};

typedef PtrToSNode Stack;

Stack CreateStack();

bool IsEmpty ( Stack S );

bool Push ( Stack S, ElementType X );

ElementType Pop ( Stack S );

void Path ( int Maze[][MAXMATRIXSIZE], int EXITROW, int EXITCOL );

int main() {
    return 0;
}


void Path ( int Maze[][MAXMATRIXSIZE], int EXITROW, int EXITCOL ) {
    struct Offsets Move[8] = 
    { {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1} };
    int Mark[MAXMATRIXSIZE][MAXMATRIXSIZE];
    Stack S;
    struct MazePosition P;
    short int Row, Col, NextRow, NextCol, Dir;
    bool Found = false;

    S = CreateStack();

    Mark[EXITROW][EXITCOL] = 1;
    P.Row = EXITROW;
    P.Col = EXITCOL;
    P.Dir = 0;
    Push(S,P);

    while ( !IsEmpty(S) && !Found ) {
        P = Pop(S);
        Row = P.Row;
        Col = P.Col;
        Dir = P.Dir;
        while ( Dir < 8 && !Found ) {
            NextRow = Row + Move[Dir].Vert;
            NextCol = Col + Move[Dir].Horiz;
            if ( NextRow == 1 && NextCol == 1 ) Found = true;
            else if ( !Maze[NextRow][NextCol] && !Mark[NextRow][NextCol] ) {
                P.Row = Row;
                P.Col = Col;
                P.Dir = Dir + 1;
                Push(S,P);
                Row = NextRow;
                Col = NextCol;
                Dir = 0;
            } else ++Dir;
        }
    }
    if (Found) {
        printf("Path\n");
        printf("Row\t|\tCol\n");
        printf("1\t|\t1\n");
        printf("%d\t|\t%d\n",Row,Col);
        while (!IsEmpty(S)) {
            P = Pop(S);
            printf("%d\t|\t%d\n",P.Row,P.Col);
        }
    } else printf("No Path\n");
}

Stack CreateStack() {
    Stack S;
    S = (Stack)malloc(sizeof(struct SNode));
    // S->Data = NULL;
    S->Next = NULL;
    return S;
}

bool IsEmpty ( Stack S ) {
    return ( S->Next == NULL );
}

bool Push ( Stack S, ElementType X ) {
    Stack tmp;
    tmp = (Stack)malloc(sizeof(struct SNode));
    tmp->Data = X;
    tmp->Next = S->Next;
    S->Next = tmp;
    return true;
}

ElementType Pop ( Stack S ) {
    if ( IsEmpty(S) ) {
        printf("Empty Stack\n");
        exit(-5);
    }
    ElementType X;
    PtrToSNode tmp = S->Next;
    X = tmp->Data;
    S->Next = tmp->Next;
    free(tmp);
    return X;
}
